Serial computation involves the implementation of a series of instructions in a specified order on a computer. One instruction executes at a time. Once the instruction is finished, a subsequent instruction is executed. The length of time required to execute the series of instructions depends on factors such as the number of instructions and complexity of the instructions.
Parallel computation performs multiple calculations or the execution of processes simultaneously. The instructions are separated into subsets, with a corresponding processing unit executing a subset of the instructions. Parallel computation decreases the length of time needed to execute the same set of instructions using serial computation. Parallel computation requires at least two processing units in order to separate and simultaneously execute each subset of the instructions. For example, a multi-core processor is a single processor with at least two processing units, called cores, which read and execute program instructions. Each core is independent and can access a shared memory concurrently. A multi-core processor executes multiple instructions on separate cores at the same time.
Numerical optimization determines the selection of a best element (based on a criterion or set of criteria) from a set of viable alternatives. Specifically, given a function with n parameters, numerical optimization generally involves determining minimum or maximum function values and the corresponding parameter values. In many instances, numerical optimizers compute partial derivatives of the given function to determine how the function values change with respect to the parameters. For example, numerical optimizers can approximate partial derivatives by computing a slope between an input point and a neighboring point.
The illustrative embodiments recognize that numeric optimizers generally perform computations sequentially. The illustrative embodiments recognize that modification of numeric optimizers to perform parallel evaluations presents numerous technical challenges. For example, modification requires understanding of complex optimization logic. The illustrative embodiments further recognize that modification of one numeric optimizer does not generally apply to other numeric optimizers.
A blackbox function is a function which itself and/or a derivative of the function cannot be expressed in analytic form using well-known mathematical operations. The illustrative embodiments recognize that numeric optimizers approximate partial derivatives of blackbox functions to determine minimum or maximum blackbox function values. For example, given a function ƒ({right arrow over (x)}) with an input vector {right arrow over (x)} having i=1 . . . n parameters, the partial derivative with respect to the ith parameter of a neighbor value {right arrow over (x)}+α{right arrow over (u)}i can be computed as
                    ∂        f                    ∂                  x          i                      ≈                            f          ⁡                      (                                          x                →                            +                              α                ⁢                                                                  ⁢                                                      u                    l                                    →                                                      )                          -                  f          ⁡                      (                          x              →                        )                              α        ,where α is a scalar quantity and {right arrow over (u)}i is a unit vector in a direction of the ith parameter. The illustrative embodiments recognize that numeric optimizers compute ƒ({right arrow over (x)}) and ƒ({right arrow over (x)}+α{right arrow over (u)}i) for i=1 . . . n to calculate the approximation of the partial derivative. The illustrative embodiments recognize that the input vector and neighboring values differ only by the amount α at the ith parameter. The illustrative embodiments further recognize that presently available numeric optimizers sequentially compute function values and partial derivatives at a single parameter before moving to the next parameter.
With the advent of quantum processors, large problems such as the problems modeled after the NP-hard traveling salesman problem, which were not practically solvable or verifiable using conventional processors, have become viably computable. To leverage quantum computing in solving such problems, the problem has to be capable of breaking down for parallel computation using quantum processors.
Numeric optimizers are also in the class of such problems that can quickly become unreasonably large for precise or conclusive computation using conventional processors. In order to leverage quantum computing to execute numeric optimizers, numeric optimizers have to be reconfigured for parallelization. The illustrative embodiments recognize that because of their sequential implementation, known numeric optimizers are particularly challenging for parallelization.